1. Field of the Invention
The present invention relates to the field of microprocessors and, more particularly, to a technique of sorting numbers to find values of maxima or minima with ordering.
2. Prior Art
In the utilization of processors, microprocessors and computer systems, it is the practice to manipulate large amounts of data represented in various forms. For most operations, the data is generally in a scalar format where operations are performed on such scalar values. For example, an adding of two numerical values entails the loading of the two values in two registers and numerically (either in integer form or floating point form) adding the two numbers. In order to speed the execution of current and subsequent instructions, many processors now employ the use of pipe-lining stages to enhance processing speed of the processor. The use of various instructions which operate on two data elements are well-known in the art.
A different type of data representation is a format referred to as "Packed Data" format. In the packed data format, a number of data elements are now grouped together into a common bit string having a specified width. For example, a packed data string may have four individual data elements, each having a specified width. Furthermore, as an example, a packed data format having 64 bits may be comprised of four 16-bit data elements. A significant advantage of having such a packed data format resides in the multiple operations which can be performed on the data string. Accordingly, with the noted example above, a packed add instruction can be invoked to add two packed data words (wherein each packed word is comprised of four data elements). In this packed addition, corresponding pairs of data elements of the two words are added. Unlike the scalar add operation, the packed add instruction in this instance would perform four different add operations (one for each pair of corresponding data elements) in parallel in response to a single instruction.
As can be appreciated, a separate set of packed instruction set would be required in order to operate on the packed data format, as well as providing the necessary operations for packing and unpacking data. Generally, the specialized instruction set can be designed into a general purpose processor at low cost, because most of the circuitry dedicated to scalar operations can be reused. However, such a processor would have significant processing advantages when packed data operations can be used instead of singular data operations.
One area where packed data operations are susceptible for improving performance is in the manipulation of multimedia data. That is, video, graphic and sound data can be manipulated in packed format using packed instructions. A variety of functions can be solved or data rearranged based on the use of the packed instruction set. One such manipulation is the sorting of numbers to determine which number from a pair of numbers is greater (or lesser) in value. A patent application titled "Method Of Sorting Signed Numbers And Solving Absolute Differences Using Packed Instructions" application Ser. No. 08/575,605, filed Dec. 20, 1995, now U.S. Pat. No. 5,907,842 describes the sorting of packed data elements from two source operands into maxima and minima operands.
This described technique compares the corresponding packed data elements from each of the operands and identifies which of the pair is greater in value. The greater values are then sorted into the maxima operand and the lesser-or-equal values are sorted into the minima operand. Although this technique sorts values correctly, there is no way of identifying from which source operand a particular value originated. That is, without some form of a tag or index associated with the selected value, only the value of the selected data is known.
Examples of using such minima and/or maxima values are well known in the area of recognition. Speech, handwriting and some image recognition functions require a comparison of patterns in which data input is compared to a value for recognition matching. In instances where a desired outcome is the selection of either the minima or the maxima, but not both, it is usually desirable to determine from which operand a particular lesser or greater value originated. In order to do this, a tag or an index will need to be associated with each data value to identify its originating location. Thus, not only is the sorting of the data required, but ordering of the selected (chosen) data must also be determined. One such example of a use of minima/maxima sorting with ordering is the use of a Viterbi algorithm (which is used in modem operations and in recognition applications) for applications which operate differently on data depending on their values with respect to a given threshold. So for example, if the data are below the threshold, one set of operations would be performed, and if the data are above the threshold, a different set of operations would be performed. Thus, the sorting operation would compare the data input to reference values to determine which is greater (or lesser) for these recognition functions.
Accordingly, the present invention describes a scheme in which a plurality of data elements are operated on in parallel to sort the maxima (or minima) from each pair of numbers into an output operand and also to identify the source location for those elements chosen.